<!DOCTYPE html>
<html>

<head>
    <meta http-equiv="content-type" content="text/html; charset=utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no">
<meta name="apple-mobile-web-app-capable" content="yes"/>
<title>E3 - Solution-23航c | pansis.io</title>
<link rel="shortcut icon" href="https://github.pansis.site/favicon.ico">
<link href="https://github.pansis.site/styles/main.css" rel="stylesheet">
<link href="//at.alicdn.com/t/c/font_1678829_b85ccgkdqkr.css" rel="stylesheet">
<link href="//cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css" rel="stylesheet">
<link rel="alternate" type="application/rss+xml" title="pansis.io » Feed" href="https://github.pansis.site/atom.xml">
        <meta name="description" content="A 鸡兔同笼2024



难度
考点




1~2
解方程，分支结构



题目分析
本题只需要解二元一次方程 {x+y=n2x+4y=m\left\lbrace\begin{matrix}x+y=n\\2x+4y=m\end{matr..." />
        <meta name="keywords" content="23航C" />
        <!-- OG -->
        <meta property="og:locale" content="zh_CN">
        <meta property="og:title" content="E3 - Solution-23航c" />
        <meta property="og:type" content="article" />
        <meta property="og:description" content="A 鸡兔同笼2024



难度
考点




1~2
解方程，分支结构



题目分析
本题只需要解二元一次方程 {x+y=n2x+4y=m\left\lbrace\begin{matrix}x+y=n\\2x+4y=m\end{matr...">
        <meta property="og:url" content="https://github.pansis.site/post/e3-solution-23-hang-c/" />
        <meta property="og:site_name" content="pansis.io">
        <meta property="og:updated_time" content="2024-03-28">
        <meta property="og:image" content="" />
        <meta property="og:image:secure_url" content="">
        <meta property="og:image:alt" content="E3 - Solution-23航c">
        <!-- Twitter (post.ejs) -->
        <meta name="twitter:card" content="summary_large_image">
        <meta name="twitter:title" content="E3 - Solution-23航c">
        <meta name="twitter:description" content="A 鸡兔同笼2024



难度
考点




1~2
解方程，分支结构



题目分析
本题只需要解二元一次方程 {x+y=n2x+4y=m\left\lbrace\begin{matrix}x+y=n\\2x+4y=m\end{matr...">
        <!-- <meta name="twitter:site" content="@WBoy0609">
        <meta name="twitter:creator" content="@WBoy0609"> -->
        <meta name="twitter:image" content="">
</head>

<body>
    <div class="main animated">
        <div class="header animated fadeInDown">
    <div class="site_title_container">
        <div class="site_title">
            <a href="https://github.pansis.site">pansis.io</a>
        </div>
    </div>
    <div class="my_socials">
        
            
        
            
        
            
        
            
        
            
        
            
        
            
        
        <a href="https://github.pansis.site/atom.xml" title="rss" target="_blank"><i class="iconfont icon-rss"></i></a>
    </div>
</div>

    <div class="header_menu">
        
            
                <a href="/" class="menu">首页</a>
            
        
            
                <a href="/tag/GWAaV2nvk/" class="menu">程序设计课程</a>
            
        
            
                <a href="/tag/24hangc" class="menu">比赛</a>
            
        
            
                <a href="/tag/L7r9STb75/" class="menu">Python教程</a>
            
        
            
                <a href="/tags" class="menu">分类</a>
            
        
        <div class="gridea-search-div">
            <form id="gridea-search-form" action="https://github.pansis.site/search/">
                <input class="gridea-search-input" autocomplete="off" spellcheck="false" name="q"/>
            </form>
        </div>
    </div>

            <div class="autopagerize_page_element">
                <div class="content">
                    <div class="post_page">
                        <div class="post animated fadeInDown">
                            <div class="post_title post_detail_title">
                                <h2>
                                    E3 - Solution-23航c
                                </h2>
                                <span class="article-info">
                                    2024-03-28, 5669 words, 26 min read
                                </span>
                            </div>
                            <div class="post_content markdown">
                                <p class="md_block">
                                    <span class="md_line md_line_start md_line_end">
                                        <h2 id="a-鸡兔同笼2024"><code>A</code> 鸡兔同笼2024</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>1~2</td>
<td>解方程，分支结构</td>
</tr>
</tbody>
</table>
<h3 id="题目分析">题目分析</h3>
<p>本题只需要解二元一次方程 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo fence="true">{</mo><mtable><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mi>x</mi><mo>+</mo><mi>y</mi><mo>=</mo><mi>n</mi></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mn>2</mn><mi>x</mi><mo>+</mo><mn>4</mn><mi>y</mi><mo>=</mo><mi>m</mi></mrow></mstyle></mtd></mtr></mtable></mrow><annotation encoding="application/x-tex">\left\lbrace\begin{matrix}x+y=n\\2x+4y=m\end{matrix}\right.</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:2.40003em;vertical-align:-0.95003em;"></span><span class="minner"><span class="mopen delimcenter" style="top:0em;"><span class="delimsizing size3">{</span></span><span class="mord"><span class="mtable"><span class="col-align-c"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.45em;"><span style="top:-3.61em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord mathdefault">x</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mord mathdefault">n</span></span></span><span style="top:-2.4099999999999997em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">2</span><span class="mord mathdefault">x</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord">4</span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mord mathdefault">m</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.9500000000000004em;"><span></span></span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span></span></span></span> ，并判断解得的 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>x</mi><mo separator="true">,</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x,y</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">x</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span></span></span></span> 是否满足以下两个要求：</p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>x</mi><mo separator="true">,</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x,y</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">x</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span></span></span></span> 都是非负整数。</li>
<li>由于求解过程使用整除，需判断 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>x</mi><mo separator="true">,</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x,y</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">x</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span></span></span></span> 带入原方程时是否能使等式成立。</li>
</ul>
<p>只有满足以上两个条件，才算原方程有非负整数解。</p>
<h3 id="示例代码">示例代码</h3>
<pre><code class="language-C">#include &lt;stdio.h&gt;

int main()
{
    int x, y, n, m;
    while (scanf(&quot;%d%d&quot;, &amp;n, &amp;m) != EOF)
    {
        x = (4 * n - m) / 2; 
        y = n - x;
        if (m % 2 || x &lt; 0 || y &lt; 0) //判断解是否满足要求
            printf(&quot;No answer\n&quot;);
        else
            printf(&quot;%d %d\n&quot;, x, y);
    }
}
</code></pre>
<h2 id="b-这是什么三角形"><code>B</code> 这是什么三角形？</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>2</td>
<td>分支结构</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-2">题目分析</h3>
<p>为了方便判断，可以在判断之前将 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>a</mi></mrow><annotation encoding="application/x-tex">a</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">a</span></span></span></span> 设为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>a</mi><mo separator="true">,</mo><mi>b</mi><mo separator="true">,</mo><mi>c</mi></mrow><annotation encoding="application/x-tex">a, b, c</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">a</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault">b</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault">c</span></span></span></span>​ 三者中的最大者。</p>
<p>优先判断特殊情况：无法组成三角形的情况和等边三角形的情况。</p>
<p>接下来通过 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msup><mi>a</mi><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">a^2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span></span></span></span> 和 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msup><mi>b</mi><mn>2</mn></msup><mo>+</mo><msup><mi>c</mi><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">b^2+c^2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.897438em;vertical-align:-0.08333em;"></span><span class="mord"><span class="mord mathdefault">b</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord"><span class="mord mathdefault">c</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span></span></span></span>​ 的大小关系判断三角形的基本形状；最后判断是否存在等腰性即可。</p>
<p>注意单词后的空格和换行符。</p>
<h3 id="示例代码-2">示例代码</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
int main()
{
	int a, b, c;
	while(scanf(&quot;%d %d %d&quot;, &amp;a, &amp;b, &amp;c) != EOF)
	{
		//保证a为三者中的最大者
		if(b &gt; a) //若b比a大，交换a,b
		{
			int t = a;
			a = b;
			b = t;
		}
		if(c &gt; a) //若c比a大，交换a,c
		{
			int t = a;
			a = c;
			c = t;
		}
		//无法组成三角形
		if(b + c &lt;= a)
		{
			printf(&quot;not a triangle\n&quot;);
			continue;
		}
		//能组成三角形
		if(a == b &amp;&amp; b == c) //先判断特殊情况：等边三角形
		{
			printf(&quot;an equilateral triangle\n&quot;);
			continue;
		}
		if(b * b + c * c &gt; a * a) //锐角三角形
			printf(&quot;an acute &quot;);
		else if(b * b + c * c == a * a) //直角三角形
			printf(&quot;a right &quot;);
		else printf(&quot;an obtuse &quot;); //钝角三角形
		//判断等腰性
		if(b == c || a == b || a == c) //存在等腰性
			printf(&quot;isosceles &quot;);
		printf(&quot;triangle\n&quot;);
	}
	return 0;
}
</code></pre>
<h2 id="c-czx-的戒指强化"><code>C</code> czx 的戒指强化</h2>
<table>
<thead>
<tr>
<th style="text-align:center">难度</th>
<th style="text-align:center">知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">2</td>
<td style="text-align:center">判断</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-3">题目分析</h3>
<p>分析题目不难发现，实际上就是判断三个数是否在某个集合内。自然可以用 <code>||</code> 连接逻辑语句来逐一判断。然而，根据集合内元素的特征，也可以直接通过判断数字落在哪个区间内来解决。</p>
<h3 id="示例代码-3">示例代码</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;

int main() {
    int n;
    scanf(&quot;%d&quot;, &amp;n);
    while (n--) {
        int a, b, c;
        scanf(&quot;%d %d %d&quot;, &amp;a, &amp;b, &amp;c);
        int res = 0;
        if (a == 100) {
            res += 0;
        } else if (a == 150) {
            res += 1;
        } else {
            res += 2;
        }

        if (b &lt;= 30) {
            res += 0;
        } else if (b &lt;= 45) {
            res += 1;
        } else {
            res += 2;
        }

        if (c &lt;= 30) {
            res += 0;
        } else if (c &lt;= 45) {
            res += 1;
        } else {
            res += 2;
        }

        printf(&quot;%d\n&quot;, res);
    }
    return 0;
}
</code></pre>
<h2 id="d-roy的军乐队排序"><code>D</code> roy的军乐队排序</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>3</td>
<td>分支，循环，数组</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-4">题目分析</h3>
<p>此题的整体思路较为简单，分为四步</p>
<ol>
<li>使用三个数组存储三行士兵的高度</li>
<li>同时遍历三个数组，纵向排序</li>
<li>判断横向是否还有序</li>
<li>按格式输出三个数组</li>
</ol>
<p>另外，printf很有很多强大的格式化输出的方法，感兴趣的同学可以参考<a href="https://www.runoob.com/cprogramming/c-function-printf.html">C 库函数 – printf() | 菜鸟教程 (runoob.com)</a></p>
<p>最后，其实对一个横向有序的队列进行纵向排序后，一定不会影响它的横向有序性，即最后一定是输出<code>true</code>，发现了这点的同学可以直接跳过第三步，直接输出<code>true</code>。</p>
<p>注意<strong>大数组要开在 <code>main</code> 函数外面</strong>作为全局变量，此外请大家<strong>使用常量来定义数组长度</strong>，不推荐使用变长数组。</p>
<h3 id="示例代码-1">示例代码 1</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
int flag;
int a1[1000005];
int a2[1000005];
int a3[1000005];

int main()
{
    // 第一步 读入士兵高度
    int n;
    scanf(&quot;%d&quot;, &amp;n);
    for (int i = 0; i &lt; n; i++)
        scanf(&quot;%d&quot;, &amp;a1[i]);
    for (int i = 0; i &lt; n; i++)
        scanf(&quot;%d&quot;, &amp;a2[i]);
    for (int i = 0; i &lt; n; i++)
        scanf(&quot;%d&quot;, &amp;a3[i]);

    // 第二步 纵向排序
    for (int i = 0; i &lt; n; i++)
    {
        int temp;
        if (a1[i] &gt; a2[i]) {temp = a1[i]; a1[i] = a2[i]; a2[i] = temp;}
        if (a1[i] &gt; a3[i]) {temp = a1[i]; a1[i] = a3[i]; a3[i] = temp;}
        // 到这里之后 a1[i]一定是最大的 但a2[i]和a3[i]之间的大小关系不确定
        if (a2[i] &gt; a3[i]) {temp = a2[i]; a2[i] = a3[i]; a3[i] = temp;}
    }

    // 第三步 判断横向是否还有序
    for (int i = 0; i &lt; n - 1; i++)
        if (a1[i] &gt; a1[i + 1])
        {
            flag = 1;
            break;
        }
    for (int i = 0; i &lt; n - 1; i++)
        if (a2[i] &gt; a2[i + 1])
        {
            flag = 1;
            break;
        }
    for (int i = 0; i &lt; n - 1; i++)
        if (a3[i] &gt; a3[i + 1])
        {
            flag = 1;
            break;
        }

    // 第四步 格式化输出三个数组
    for (int i = 0; i &lt; n; i++)
        printf(&quot;%-7d&quot;, a1[i]);
    printf(&quot;\n&quot;);
    for (int i = 0; i &lt; n; i++)
        printf(&quot;%-7d&quot;, a2[i]);
    printf(&quot;\n&quot;);
    for (int i = 0; i &lt; n; i++)*
        printf(&quot;%-7d&quot;, a3[i]);
    printf(&quot;\n&quot;);

    if (flag == 0)
        printf(&quot;true&quot;);
    else
        printf(&quot;false&quot;);
}
</code></pre>
<h3 id="示例代码-2">示例代码 2</h3>
<p><strong>函数版本</strong></p>
<p>我们可以将重复的功能（读入一个数组，输出一个数组，判断数组是否有序）包装为函数。此种做法可以显著提升代码的可读性，且debug更加方便，也不易出错。</p>
<p>也请同学们关注全局变量 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi mathvariant="normal">（</mi><mi>n</mi><mo separator="true">,</mo><mi>f</mi><mi>l</mi><mi>a</mi><mi>g</mi><mo separator="true">,</mo><mi>a</mi><mn>1</mn><mo separator="true">,</mo><mi>a</mi><mn>2</mn><mo separator="true">,</mo><mi>a</mi><mn>3</mn><mi mathvariant="normal">）</mi></mrow><annotation encoding="application/x-tex">（n, flag, a1, a2, a3）</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord cjk_fallback">（</span><span class="mord mathdefault">n</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault" style="margin-right:0.10764em;">f</span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mord mathdefault">a</span><span class="mord mathdefault" style="margin-right:0.03588em;">g</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault">a</span><span class="mord">1</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault">a</span><span class="mord">2</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault">a</span><span class="mord">3</span><span class="mord cjk_fallback">）</span></span></span></span>​ 和函数的配合使用，即函数中可以直接修改全局变量的值，减少了函数的传参，也让代码更加简洁。</p>
<pre><code class="language-c">#include &lt;stdio.h&gt;
int n;
int flag;
int a1[1000005];
int a2[1000005];
int a3[1000005];

void read(int a[]) {
    for (int i = 0; i &lt; n; i++)
		scanf(&quot;%d&quot;, &amp;a[i]);
}

void print(int a[]) {
    for (int i = 0; i &lt; n; i++)
		printf(&quot;%-7d&quot;, a[i]);
    printf(&quot;\n&quot;);
}

void swap(int a1[], int a2[], int i) {
	int temp = a1[i];
	a1[i] = a2[i];
	a2[i] = temp;
}

void sort(int i) {
	int temp;
	if (a1[i] &gt; a2[i]) 
		swap(a1, a2, i);
	if (a1[i] &gt; a3[i]) 
		swap(a1, a3, i);
    //到这里之后 a1[i]一定是最大的 但a2[i]和a3[i]之间的大小关系不确定
	if (a2[i] &gt; a3[i]) 
		swap(a2, a3, i);
}

void judge(int a[]) {
	for (int i = 0; i &lt; n - 1; i++) {
		if (a[i] &gt; a[i + 1]) {
			flag = 1;
			return;
		}
	}
}

int main()
{
    // 第一步 读入士兵高度
	scanf(&quot;%d&quot;, &amp;n);
	read(a1);
	read(a2);
	read(a3);
	// 第二步 纵向排序
	for (int i = 0; i &lt; n; i++)
		sort(i);
	//第三步 判断横向是否还有序
    judge(a1);
    judge(a2);
    judge(a3);
    //第四步 格式化输出三个数组
	print(a1);
	print(a2);
	print(a3);
	if (flag == 0)
		printf(&quot;true&quot;);
	else 
		printf(&quot;false&quot;);
}
</code></pre>
<h2 id="e-czx-的问答游戏"><code>E</code> czx 的问答游戏</h2>
<table>
<thead>
<tr>
<th style="text-align:center">难度</th>
<th style="text-align:center">知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">3</td>
<td style="text-align:center">循环，条件语句</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-5">题目分析</h3>
<p>不难发现，要解决这个问题，可以分两步来解决：</p>
<ol>
<li>找到满足条件（<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>a</mi><mi>i</mi></msub><mo>≤</mo><mn>10</mn></mrow><annotation encoding="application/x-tex">a_i \leq 10</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7859700000000001em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">i</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span><span class="mord">0</span></span></span></span>）的 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>b</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">b_i</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.84444em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathdefault">b</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">i</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> 最大值 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi><mi>a</mi><mi>x</mi><mi>b</mi></mrow><annotation encoding="application/x-tex">maxb</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault">m</span><span class="mord mathdefault">a</span><span class="mord mathdefault">x</span><span class="mord mathdefault">b</span></span></span></span>；</li>
<li>找到所有满足 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>a</mi><mi>i</mi></msub><mo>≤</mo><mn>10</mn></mrow><annotation encoding="application/x-tex">a_i \leq 10</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7859700000000001em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">i</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span><span class="mord">0</span></span></span></span> 且 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>b</mi><mi>i</mi></msub><mo>=</mo><mi>m</mi><mi>a</mi><mi>x</mi><mi>b</mi></mrow><annotation encoding="application/x-tex">b_i = maxb</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.84444em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathdefault">b</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">i</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault">m</span><span class="mord mathdefault">a</span><span class="mord mathdefault">x</span><span class="mord mathdefault">b</span></span></span></span> 的 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.65952em;vertical-align:0em;"></span><span class="mord mathdefault">i</span></span></span></span>.</li>
</ol>
<p>用两个循环即可解决这个问题。第一个循环寻找最大值，并用一个变量来实时记录更新；第二个循环寻找所有满足条件的编号，并输出。</p>
<h3 id="示例代码-1-2">示例代码 1</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;

#define N 1005

int num, res[N], a[N], b[N];

int main() {
    int t;
    scanf(&quot;%d&quot;, &amp;t);
    while (t--) {
        int n, maxx = -1;
        scanf(&quot;%d&quot;, &amp;n);
        for (int i = 1; i &lt;= n; i++) {
            scanf(&quot;%d %d&quot;, &amp;a[i], &amp;b[i]);
            if (a[i] &lt;= 10 &amp;&amp; b[i] &gt; maxx) {
                maxx = b[i];
            }
        }
        num = 0;
        for (int i = 1; i &lt;= n; i++) {
            if (a[i] &lt;= 10 &amp;&amp; b[i] == maxx) {
                res[num++] = i;
            }
        }
        printf(&quot;%d\n&quot;, num);
        for (int i = 0; i &lt; num; i++) {
            printf(&quot;%d &quot;, res[i]);
        }
        printf(&quot;\n&quot;); // 注意最后换行
    }
    return 0;
}
</code></pre>
<h3 id="示例代码-2-2">示例代码 2</h3>
<p>与代码一思路类似，找最大值和记录最大值出现位置写在了同一个循环里。</p>
<pre><code class="language-c">#include&lt;stdio.h&gt;
int main()
{
	int t;
	scanf(&quot;%d&quot;, &amp;t);
	while(t--)
	{
		int n, k = 0, id[505], max = 0;
		scanf(&quot;%d&quot;, &amp;n);
		for(int i = 1; i &lt;= n; ++i)
		{
			int a, b;
			scanf(&quot;%d%d&quot;, &amp;a, &amp;b);
			if(a &lt;= 10)
            {
				if(b == max) id[k++] = i;
				else if(b &gt; max) 
                {
                    max = b;
                    k = 0;
                    id[k++] = i;
                }
            }
		}
		printf(&quot;%d\n&quot;, k);
		for(int i = 0; i &lt; k; ++i)
			printf(&quot;%d &quot;, id[i]);
		printf(&quot;\n&quot;);
	}
	return 0;
}
</code></pre>
<h2 id="f-匹配星期"><code>F</code> 匹配星期</h2>
<table>
<thead>
<tr>
<th style="text-align:left">难度</th>
<th style="text-align:left">考点</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:left">3~4</td>
<td style="text-align:left">结构化编程，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>Z</mi><mi>e</mi><mi>l</mi><mi>l</mi><mi>e</mi><mi>r</mi></mrow><annotation encoding="application/x-tex">Zeller</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.07153em;">Z</span><span class="mord mathdefault">e</span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mord mathdefault">e</span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span></span></span></span> 公式</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-6">题目分析</h3>
<p><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>Z</mi><mi>e</mi><mi>l</mi><mi>l</mi><mi>e</mi><mi>r</mi></mrow><annotation encoding="application/x-tex">Zeller</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.07153em;">Z</span><span class="mord mathdefault">e</span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mord mathdefault">e</span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span></span></span></span> 公式：</p>
<p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>w</mi><mo>=</mo><mo>(</mo><mo>⌊</mo><mfrac><mi>c</mi><mn>4</mn></mfrac><mo>⌋</mo><mo>−</mo><mn>2</mn><mi>c</mi><mo>+</mo><mi>y</mi><mo>+</mo><mo>⌊</mo><mfrac><mi>y</mi><mn>4</mn></mfrac><mo>⌋</mo><mo>+</mo><mo>⌊</mo><mfrac><mrow><mn>13</mn><mo>(</mo><mi>m</mi><mo>+</mo><mn>1</mn><mo>)</mo></mrow><mn>5</mn></mfrac><mo>⌋</mo><mo>+</mo><mi>d</mi><mo>−</mo><mn>1</mn><mo>)</mo><mtext> </mtext><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi></mrow><mtext> </mtext><mn>7</mn></mrow><annotation encoding="application/x-tex">w=(\lfloor\frac{c}{4}\rfloor-2c+y+\lfloor\frac{y}{4}\rfloor+\lfloor\frac{13(m
+1)}{5}\rfloor+d-1)\bmod7
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.02691em;">w</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1.7935600000000003em;vertical-align:-0.686em;"></span><span class="mopen">(</span><span class="mopen">⌊</span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.10756em;"><span style="top:-2.314em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">4</span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.677em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord mathdefault">c</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.686em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mclose">⌋</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.72777em;vertical-align:-0.08333em;"></span><span class="mord">2</span><span class="mord mathdefault">c</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.7777700000000001em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1.7935599999999998em;vertical-align:-0.686em;"></span><span class="mopen">⌊</span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.1075599999999999em;"><span style="top:-2.314em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">4</span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.677em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord mathdefault" style="margin-right:0.03588em;">y</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.686em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mclose">⌋</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:2.113em;vertical-align:-0.686em;"></span><span class="mopen">⌊</span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.427em;"><span style="top:-2.314em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">5</span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.677em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">1</span><span class="mord">3</span><span class="mopen">(</span><span class="mord mathdefault">m</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord">1</span><span class="mclose">)</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.686em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mclose">⌋</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">d</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mspace" style="margin-right:0.05555555555555555em;"></span><span class="mbin"><span class="mord"><span class="mord mathrm">m</span><span class="mord mathrm">o</span><span class="mord mathrm">d</span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mspace" style="margin-right:0.05555555555555555em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">7</span></span></span></span></span></p>
<p>其中 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>w</mi></mrow><annotation encoding="application/x-tex">w</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.02691em;">w</span></span></span></span> 为星期；<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>c</mi></mrow><annotation encoding="application/x-tex">c</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">c</span></span></span></span> 为年的前两位；<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>y</mi></mrow><annotation encoding="application/x-tex">y</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span></span></span></span> 为年的后两位；<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">m</span></span></span></span> 为月；<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>d</mi></mrow><annotation encoding="application/x-tex">d</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault">d</span></span></span></span> 为日。</p>
<p>别忘记每年的 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn><mi mathvariant="normal">、</mi><mn>2</mn></mrow><annotation encoding="application/x-tex">1、2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span><span class="mord cjk_fallback">、</span><span class="mord">2</span></span></span></span> 月要当做前一年的 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>13</mn><mi mathvariant="normal">、</mi><mn>14</mn></mrow><annotation encoding="application/x-tex">13、14</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span><span class="mord">3</span><span class="mord cjk_fallback">、</span><span class="mord">1</span><span class="mord">4</span></span></span></span> 月来计算。</p>
<h3 id="示例代码-4">示例代码</h3>
<pre><code class="language-c++">#include&lt;stdio.h&gt;
int main()
{
	int n;
	scanf(&quot;%d&quot;, &amp;n);
	for(int i = 1; i &lt;= n; i++)
	{
		int yyyy, mm, dd, w;
		scanf(&quot;%d.%d.%d%d&quot;, &amp;yyyy, &amp;mm, &amp;dd, &amp;w);
		if (mm &lt;= 2)
		{
			yyyy--;
			mm += 12;
		}
		int c = yyyy / 100;
		int y = yyyy % 100;
		if((c / 4 - 2 * c + y + y / 4 + 13 * (mm + 1) / 5 + dd - 1 - w) % 7 == 0)
            printf(&quot;YES\n&quot;);
		else
            printf(&quot;NO\n&quot;);
	}
	return 0;
}

</code></pre>
<p><strong>思考一下：为什么星期的判断写成 <code>if((......-w)%7==0)</code> 而不是 <code>if(......%7==w)</code> 呢？</strong></p>
<p>不妨让计算机输出一下 <code>(-5)/3</code>,<code>(-5)/(-3)</code>,<code>5/(-3)</code>,<code>(-5)%3</code>,<code>(-5)%(-3)</code>,<code>5%(-3)</code> 的值，看看和你想的有没有差距？</p>
<p>这是因为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>Z</mi><mi>e</mi><mi>l</mi><mi>l</mi><mi>e</mi><mi>r</mi></mrow><annotation encoding="application/x-tex">Zeller</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.07153em;">Z</span><span class="mord mathdefault">e</span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mord mathdefault">e</span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span></span></span></span> 公式对 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>7</mn></mrow><annotation encoding="application/x-tex">7</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">7</span></span></span></span> 取模前的数有可能是一个负数，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>C</mi></mrow><annotation encoding="application/x-tex">C</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.07153em;">C</span></span></span></span> 语言中的整除是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>⌈</mo></mrow><annotation encoding="application/x-tex">\lceil</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">⌈</span></span></span></span> 对 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>0</mn></mrow><annotation encoding="application/x-tex">0</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">0</span></span></span></span> 取整 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>⌋</mo></mrow><annotation encoding="application/x-tex">\rfloor</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mclose">⌋</span></span></span></span>，具体表现为结果为正数时向下取整，结果为负时向上取整，并且取模结果与整除结果相一致，也就是说 <code>(a-a/b*b)==(a%b)</code> 恒成立。</p>
<p>或者我们可以理解成：<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>C</mi></mrow><annotation encoding="application/x-tex">C</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.07153em;">C</span></span></span></span> 语言中的 <code>a%b</code> 和 <code>a/b</code> 都是先对 <code>a</code> 和 <code>b</code> 取绝对值运算，再考虑符号正负。<code>a%b</code> 符号与 <code>a</code> 一致；<code>a/b</code> 是 “ 同号为正，异号为负 ”。</p>
<p>回到这道题里也就是说，如果取模前 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>Z</mi><mi>e</mi><mi>l</mi><mi>l</mi><mi>e</mi><mi>r</mi></mrow><annotation encoding="application/x-tex">Zeller</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.07153em;">Z</span><span class="mord mathdefault">e</span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mord mathdefault">e</span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span></span></span></span> 公式的结果是一个负数，取模后一定也不是正数（可能是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>0</mn></mrow><annotation encoding="application/x-tex">0</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">0</span></span></span></span>），因此写成第一种才正确。</p>
<h2 id="g-判断缓存是否命中"><code>G</code> 判断缓存是否命中</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>4</td>
<td>模拟，循环</td>
</tr>
</tbody>
</table>
<h3 id="大致题意">大致题意</h3>
<p>给定缓存大小和一段缓存序列，使用最近最久未使用（LRU）策略判断每个缓存请求是否命中。</p>
<h3 id="题目分析-7">题目分析</h3>
<p>这个题目的信息量很大，如果是做题的话，可以忽略背景信息，直接阅读题目描述。</p>
<p>根据题目的要求，我们可以用一个一维数组来模拟缓存（大小应该比缓存大小稍大一些，避免数组越界），将下标 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn><mo separator="true">,</mo><mn>2</mn><mo separator="true">,</mo><mo>⋯</mo><mi>N</mi></mrow><annotation encoding="application/x-tex">1,2,\cdots N</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8777699999999999em;vertical-align:-0.19444em;"></span><span class="mord">1</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">2</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="minner">⋯</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault" style="margin-right:0.10903em;">N</span></span></span></span> 作为缓存有效的存储位置。初始时将缓存中的地址都填充为无效的地址（-1）。每当一个请求到来的时候，我们首先遍历数组，查找请求地址是否在数组中。如果地址在数组中，则输出 <code>YES {该地址在数组中的位置}</code>，然后将该地址移到数组的首部，将原来排在该地址前面的地址依次向后移动一位。如果地址不在缓存中，则输出 <code>NO</code>，然后在数组的首部插入该地址，数组中的其他地址依次向后移动一位。原来位于数组中最后一个位置的地址将被移出数组，从而被丢弃。</p>
<h3 id="示例代码-1-3">示例代码 1</h3>
<pre><code class="language-c">#include&lt;stdio.h&gt;
#define N 100005
int arr[N];
int main() {
	int n, l;
	int loc = -1;
	scanf(&quot;%d%d&quot;, &amp;n, &amp;l);
    for (int i = 1; i &lt;= n; ++i) {
       arr[i] = -1; // 将数组下标 1-n 存储的地址设置为无效地址，注意数组的下标 0（第一个元素）未被使用
    }
	for (int i = 1; i &lt;= l; ++i) {
		int addr;
		scanf(&quot;%d&quot;, &amp;addr); // 读入一个新的地址
		int flag = 0;
		int loc;
		for (int j = 1; j &lt;= n; ++j) {
			if (arr[j] == addr) { // 如果缓存中有该地址
				flag = 1; // 设置命中标记
				loc = j;
				for (int k = j - 1; k &gt;= 1; --k) {
					arr[k + 1] = arr[k]; // 排在该地址的前面的地址依次向后移动一位，注意应该从下标较大的地址开始移动，否则
				} // 下标较大的地址将被下标较小的地址覆盖！！！
				arr[1] = addr; // 将命中的地址移动到数组下标 1 对应的位置。
				break;
			}
		}
		if (flag) { // 如果命中
			printf(&quot;YES %d\n&quot;, loc);
		} else { 
			printf(&quot;NO\n&quot;);
		}
		if (!flag) { // 未命中，将原来在缓存中的地址依次向右移动一位，仍然是从下标较大的地址开始移动，注意原来下标为 n 的地址被丢弃
			for (int j = n - 1; j &gt;= 1; --j) {
				arr[j + 1] = arr[j];
			}
			arr[1] = addr; // 将未命中的地址放置到数组下标 1 对应的位置
		}
	}
	return 0;
}

</code></pre>
<h3 id="示例代码-2-3">示例代码 2</h3>
<p>宋老师的版本，使用了函数简化代码。</p>
<pre><code class="language-c">#include &lt;stdio.h&gt;

// 第四步：把函数原型补充上
int lookupX(int);
int sizeN(void);
void insertX(int, int);

int cacheN[1005]; //数组长度定义稍微多几个
int N, L;

// 分析的第一步：画图分析样例，给出求解思路，这步很关键
// 分析的第二步：设计算法，因为第一部的基础已经很好，我就直接写在主函数main中
int main()
{
    int i, x;

	scanf(&quot;%d%d&quot;, &amp;N, &amp;L);
	for(i=1; i&lt;=N; i++)
	    cacheN[i] = -1; //缓存里每一个位置初始化为-1，表示初始状态下没有存储任何地址

	for(i=1; i&lt;=L; i++)
	{
	    scanf(&quot;%d&quot;, &amp;x);
	    int pos = lookupX(x); // 在cacheN里查找x是否存在，存在返回位置，不存在返回0
                              // cacheN是全局数组，可以在任意地方访问，不需要作为参数
	    int size_N = sizeN(); // 计算cacheN里存有多少个地址

	    if(pos == 0)
        {
            printf(&quot;NO\n&quot;);
            insertX(x, size_N+1); // cacheN里地址有size_N个，把地址x添加到缓存第1位，前size_N个地址依序后移1个位置，函数执行完后缓存里地址有size_N+1个（如果越界，也没有关系，越界的值不会用）
            // 系统学习函数和数组后，可以看到，这样设计函数并不是很好。需要访问的数组（地址）也应该作为函数参数，让函数模块化特征更好。
        }
        else
        {
            printf(&quot;YES %d\n&quot;, pos);
            insertX(x, pos); // 把地址x（在位置pos处）添加到缓存第1位，前pos-1个地址依序后移1个位置，pos+1后面的地址不用变
        }

//for test, 第五步，样例数据错误，开始debug，输出中间结果，分析误地方，这步最艰难
        /*
            for(int j=1; j&lt;N; j++)
            {
                printf(&quot; %d&quot;, cacheN[j]);
            }
            printf(&quot;\n&quot;);
        */
        // 每次请求后，把缓存里的数据都输出，对照样例数据（如果样例数据简单，自己构造更通用的数据），分析自己的错误出现在哪一步，逐步排查，发现一处错误，改进一处，把错误逐步消亡。
        // 排查完所有错误并改正后，结果正确。最后需要把这些输出中间结果的代码都删除，或注释掉。
	}
	return 0;
}

// 第三步，各个函数（子问题）的独立设计
int lookupX(int x)
{
    int pos = 0;
    for(int i=1; i&lt;=N &amp;&amp; cacheN[i] != -1; i++)
    {
        if(x == cacheN[i])
        {
            pos = i;
            break;
        }
    }

    return pos;
}

int sizeN()
{
    int i;
    for(i=1; i&lt;=N; i++)
    {
        if(cacheN[i] == -1)
            break;
    }
    return i-1;
}
/*
后记
效率可以更高些，如下：
请求N次前，顺序查找，如示例。
请求N次后，倒序查找，缓存中的地址不等于-1就结束循环。因为请求若干次后，数组通常已经满了，倒序查找第一次就结束了，自然效率高。
事实上，size_N是非减增长的，缓存满了后， size_N=N保持不变，后面的请求中，缓存都是满的状态，无需再计算sizeN这个函数。
追求，永无止境！
*/

// 前pos-1个地址依序后移1个位置，把地址x添加到缓存第1位，pos+1后面的地址不用变
void insertX(int x, int pos)
{
    for(int i=pos; i&gt;=2; i--)
        cacheN[i] = cacheN[i-1];

    cacheN[1] = x;
}
</code></pre>
<h2 id="h-小霁的时间乱流plus"><code>H</code> 小霁的时间乱流plus++</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>4~5</td>
<td>进制转换</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-8">题目分析</h3>
<p>本题在分钟进位小时，小时进位天数较为简单。</p>
<p>但在天数进位月份时，需要考虑每月天数不同也需要考虑闰年的因素。</p>
<p>闰年的规定是 <strong>“能被400整除，或者能被4整除但不能被100整除的是闰年”</strong>，转化为C语言就是<code>((y % 4 == 0 &amp;&amp; y % 100 != 0) || y % 400 == 0)</code>，如果该条件式成立，则y是闰年，反之不是闰年。<br>
具体的乱流中的时间调整方式已在题目中详细给出，此处不再赘述。</p>
<h3 id="示例代码-5">示例代码</h3>
<pre><code class="language-c">#include&lt;stdio.h&gt;
int main()
{

	int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; //定义每月天数
	int n;//数据组数
	int y, mon, d, h, min; //年、月、日、时、分
	int tempday;
	scanf(&quot;%d&quot;, &amp;n);
	for (int i = 0; i &lt; n; ++i)
	{
		scanf(&quot;%d.%d.%d %d:%d&quot;, &amp;y, &amp;mon, &amp;d, &amp;h, &amp;min); //输入乱流中的时间
		h += (min / 60);
		min %= 60;
		d += (h / 24);
		h %= 24; //计算正常的小时数、分钟数，并向天数进位
		y += (mon - 1) / 12;
		mon = (mon - 1) % 12 + 1;//先将月份向年份进位
		tempday = months[mon] + (((y % 4 == 0 &amp;&amp; y % 100 != 0) || y % 400 == 0) &amp;&amp; (mon == 2)); //计算当前的y和mon对应的当月天数
		//(((y % 4 == 0 &amp;&amp; y % 100 != 0) || y % 400 == 0)&amp;&amp;(mon==2))用于判定当前的y和mon是否是闰年的2月，若条件式成立，则条件式的值为1，在28天的基础上加1天。
		while (d &gt; tempday) //如果天数超过该月份的天数
		{
			d -= tempday;
			mon++;//天数减去该月天数，月份加一
			y += (mon - 1) / 12;
			mon = (mon - 1) % 12 + 1;//若月份大于12，则向年份进位
			tempday = months[mon] + (((y % 4 == 0 &amp;&amp; y % 100 != 0) || y % 400 == 0) &amp;&amp; (mon == 2)); //计算当前的y和mon对应的当月天数
		}
		printf(&quot;%04d.%02d.%02d %02d:%02d\n&quot;, y, mon, d, h, min);
	}
    return 0;
}
</code></pre>
<h2 id="i-对称的-2k1-进制-2024"><code>I</code> 对称的 2k+1 进制 2024</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>5</td>
<td>平衡进制</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-9">题目分析</h3>
<p>可以先将数码存在一个字符数组中等待调用。对于平衡 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>2</mn><mi>k</mi><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">2k+1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord">2</span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span> 进制，可以先将其转换为普通的  <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>2</mn><mi>k</mi><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">2k+1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord">2</span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span> 进制，再进行转换。<br>
注意到普通进制的数码是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>0</mn></mrow><annotation encoding="application/x-tex">0</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">0</span></span></span></span> 到 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>2</mn><mi>k</mi></mrow><annotation encoding="application/x-tex">2k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord">2</span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span></span></span></span>，平衡进制的数码是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>−</mo><mi>k</mi></mrow><annotation encoding="application/x-tex">-k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord">−</span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span></span></span></span> 到 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span></span></span></span> 。若一个数在转换前后的数码都在 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>0</mn></mrow><annotation encoding="application/x-tex">0</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">0</span></span></span></span> 至 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span></span></span></span> 内，则无需转换，因此转换的主要对象是大于 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span></span></span></span> 的数码。对于普通 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>2</mn><mi>k</mi><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">2k+1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord">2</span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span> 进制的数码 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi><mo separator="true">,</mo><mi>m</mi><mo>&gt;</mo><mi>k</mi></mrow><annotation encoding="application/x-tex">m,m&gt;k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7335400000000001em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">m</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault">m</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">&gt;</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span></span></span></span>，可以将这一位数转换为平衡进制数码 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi><mo>−</mo><mo>(</mo><mn>2</mn><mi>k</mi><mo>+</mo><mn>1</mn><mo>)</mo></mrow><annotation encoding="application/x-tex">m-(2k+1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">m</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord">2</span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span></span></span></span> 并且令高位增加 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn></mrow><annotation encoding="application/x-tex">1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span>，保持相等。对于整数内的运算，则可以类比，使用“整数位本身减 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>2</mn><mi>k</mi><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">2k+1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord">2</span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span>，高位进一”的方法，这样就实现了转换。<br>
注意到平衡进制正负数只要数码取反即可，因此可将负数先化为正数，再逐位取相反数即可。</p>
<h3 id="示例代码-1-4">示例代码 1</h3>
<pre><code class="language-c">#include&lt;stdio.h&gt;
char s[20] = {'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
// char s[20] = &quot;IHGFEDCBA0123456789&quot;;
int ans[20], cnt;
int main() {
	int n, k;
	scanf(&quot;%d%d&quot;, &amp;n, &amp;k);
	if (n == 0) {
		printf(&quot;0\n&quot;);
	} else if (n &gt; 0) {
		while (n &gt; 0) {
			ans[cnt] = n % (2 * k + 1);
			n = n / (2 * k + 1);
			cnt++;
		}
		for (int i = 0; i &lt;= cnt - 1; i++) {
			if (ans[i] &gt;= k + 1) {
				ans[i] -= (2 * k + 1);
				ans[i + 1]++;
				if (i == cnt - 1)cnt++;
			}
		}
		for (int i = cnt - 1; i &gt;= 0; i--) {
			printf(&quot;%c&quot;, s[9 + ans[i]]);
		}
	} else if (n &lt; 0) {
		n = -n;
		while (n &gt; 0) {
			ans[cnt] = n % (2 * k + 1);
			n = n / (2 * k + 1);
			cnt++;
		}
		for (int i = 0; i &lt;= cnt - 1; i++) {
			if (ans[i] &gt;= k + 1) {
				ans[i] -= (2 * k + 1);
				ans[i + 1]++;
				if (i == cnt - 1)cnt++;
			}
		}
		for (int i = cnt - 1; i &gt;= 0; i--) {
			printf(&quot;%c&quot;, s[9 - ans[i]]);
		}
	}
	return 0;
}
</code></pre>
<h3 id="示例代码-2-4">示例代码 2</h3>
<p>推荐下节课学习了函数与递归之后再来回顾本题的本解法。</p>
<p>设 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">n</span></span></span></span> 的平衡 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>2</mn><mi>k</mi><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">2k+1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord">2</span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span> 进制的最低位为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">m</span></span></span></span>，则 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mfrac><mrow><mi>n</mi><mo>−</mo><mi>m</mi></mrow><mrow><mn>2</mn><mi>k</mi><mo>+</mo><mn>1</mn></mrow></mfrac></mrow><annotation encoding="application/x-tex">\dfrac{n-m}{2k+1}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:2.0296600000000002em;vertical-align:-0.7693300000000001em;"></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.2603300000000002em;"><span style="top:-2.314em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">2</span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord">1</span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.677em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord mathdefault">m</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.7693300000000001em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span></span></span></span> 的平衡 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>2</mn><mi>k</mi><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">2k+1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord">2</span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span> 进制与 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">m</span></span></span></span> 拼接后就是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">n</span></span></span></span> 的平衡 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>2</mn><mi>k</mi><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">2k+1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord">2</span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span> 进制表示。</p>
<p>例如 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>−</mo><mn>17</mn></mrow><annotation encoding="application/x-tex">-17</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.72777em;vertical-align:-0.08333em;"></span><span class="mord">−</span><span class="mord">1</span><span class="mord">7</span></span></span></span> 的平衡 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>3</mn></mrow><annotation encoding="application/x-tex">3</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">3</span></span></span></span> 进制的最低位为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn></mrow><annotation encoding="application/x-tex">1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span>，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mfrac><mrow><mo>−</mo><mn>17</mn><mo>−</mo><mn>1</mn></mrow><mn>3</mn></mfrac><mo>=</mo><mo>−</mo><mn>6</mn></mrow><annotation encoding="application/x-tex">\dfrac{-17-1}{3}=-6</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:2.00744em;vertical-align:-0.686em;"></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.32144em;"><span style="top:-2.314em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">3</span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.677em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">−</span><span class="mord">1</span><span class="mord">7</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord">1</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.686em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.72777em;vertical-align:-0.08333em;"></span><span class="mord">−</span><span class="mord">6</span></span></span></span> 的平衡 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>3</mn></mrow><annotation encoding="application/x-tex">3</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">3</span></span></span></span> 进制表示为 <code>A10</code>，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>−</mo><mn>17</mn></mrow><annotation encoding="application/x-tex">-17</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.72777em;vertical-align:-0.08333em;"></span><span class="mord">−</span><span class="mord">1</span><span class="mord">7</span></span></span></span> 的平衡 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>3</mn></mrow><annotation encoding="application/x-tex">3</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">3</span></span></span></span> 进制表示为 <code>A101</code>。</p>
<p>可以使用递归函数的做法解决本题。</p>
<pre><code class="language-c">#include &lt;stdio.h&gt;
void f(int n, int k) //函数功能：输出n的平衡k进制表示
{
	int m = (n % k + k) % k; //求出普通k进制的最低位
	if(m &gt; k / 2) m -= k; //求出平衡k进制的最低位
	//上面可以写作 int m = (n % k + k + k / 2) % k - k / 2;
	if(n - m) //若(n-m)/k不为0，说明高位还没有计算完
		f((n - m) / k, k); //递归输出(n-m)/k的平衡2k+1进制表示
	printf(&quot;%c&quot;, m &lt; 0 ? 'A' - m - 1 : '0' + m); //输出n的平衡k进制的最低位
}
int main()
{
	int n, k;
	scanf(&quot;%d%d&quot;, &amp;n, &amp;k);
	f(n, 2 * k + 1);
	return 0;
}
</code></pre>
<h2 id="j-魅力四射"><code>J</code> 魅力四射</h2>
<table>
<thead>
<tr>
<th>难度</th>
<th>考点</th>
</tr>
</thead>
<tbody>
<tr>
<td>6</td>
<td>贪心</td>
</tr>
</tbody>
</table>
<h3 id="题目分析-10">题目分析</h3>
<p>​	首先，我们可以看出有区间改变后的答案一定是不降的。</p>
<p>​	另外，由简单贪心，我们可以知道，选取的区间的左右端点处的数一定被统计到答案里。</p>
<p>​	如果我们用 <code>res[i]</code> 数组来记录位置 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn><mo>∼</mo><mi>i</mi></mrow><annotation encoding="application/x-tex">1 \sim i</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">∼</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.65952em;vertical-align:0em;"></span><span class="mord mathdefault">i</span></span></span></span> 中，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>c</mi><mi>n</mi><msub><mi>t</mi><mi>x</mi></msub><mo>−</mo><mi>c</mi><mi>n</mi><msub><mi>t</mi><mrow><mi>x</mi><mo>+</mo><mi>k</mi></mrow></msub></mrow><annotation encoding="application/x-tex">cnt_ {x} - cnt _ {x + k}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.76508em;vertical-align:-0.15em;"></span><span class="mord mathdefault">c</span><span class="mord mathdefault">n</span><span class="mord"><span class="mord mathdefault">t</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.151392em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">x</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.8234109999999999em;vertical-align:-0.208331em;"></span><span class="mord mathdefault">c</span><span class="mord mathdefault">n</span><span class="mord"><span class="mord mathdefault">t</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3361079999999999em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">x</span><span class="mbin mtight">+</span><span class="mord mathdefault mtight" style="margin-right:0.03148em;">k</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.208331em;"><span></span></span></span></span></span></span></span></span></span> 的最大值（此处记录答案相当于为区间加 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span></span></span></span> 后为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>x</mi><mo>+</mo><mi>k</mi></mrow><annotation encoding="application/x-tex">x + k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">x</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span></span></span></span>），那么对答案取 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi><mi>a</mi><mi>x</mi></mrow><annotation encoding="application/x-tex">max</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">m</span><span class="mord mathdefault">a</span><span class="mord mathdefault">x</span></span></span></span> 一定不劣且不会漏解。</p>
<p>​	再通过一个 <code>sum</code> 数组记录每个数在数组中最开始出现的次数，那么答案是</p>
<p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi><mi>a</mi><msup><mi>x</mi><mo>∗</mo></msup><mo>{</mo><mi>s</mi><mi>u</mi><mi>m</mi><mo>[</mo><mi>x</mi><mo>+</mo><mi>k</mi><mo>]</mo><mo>+</mo><mi>r</mi><mi>e</mi><mi>s</mi><mo>[</mo><mi>x</mi><mo>+</mo><mi>k</mi><mo>]</mo><mo>}</mo></mrow><annotation encoding="application/x-tex">max ^ {*} \lbrace sum[x + k] + res[x + k] \rbrace
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">m</span><span class="mord mathdefault">a</span><span class="mord"><span class="mord mathdefault">x</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.738696em;"><span style="top:-3.113em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">∗</span></span></span></span></span></span></span></span></span><span class="mopen">{</span><span class="mord mathdefault">s</span><span class="mord mathdefault">u</span><span class="mord mathdefault">m</span><span class="mopen">[</span><span class="mord mathdefault">x</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mclose">]</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span><span class="mord mathdefault">e</span><span class="mord mathdefault">s</span><span class="mopen">[</span><span class="mord mathdefault">x</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mclose">]</span><span class="mclose">}</span></span></span></span></span></p>
<h3 id="示例代码-6">示例代码</h3>
<pre><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;math.h&gt;
#include &lt;stdlib.h&gt;

#define max(a, b) (((a) &gt; (b)) ? (a) : (b))
#define maxn 4000005
#define N 2000000

int arr[maxn];
int sum[maxn], res[maxn];
int n, k, ans;

int main() {
	scanf(&quot;%d %d&quot;, &amp;n, &amp;k);
	for(int i = 1; i &lt;= n; i++) {
		scanf(&quot;%d&quot;, &amp;arr[i]);
		sum[arr[i] + N]++;
		ans = max(ans, sum[arr[i] + N]); 
	}
	
	for(int i = 1; i &lt;= n; i++) {
		res[arr[i] + k + N]++;
		if(res[arr[i] + N]) res[arr[i] + N]--;
		ans = max(ans, sum[arr[i] + k + N] + res[arr[i] + k + N]);
	}
	printf(&quot;%d\n&quot;, ans);
    return 0;
}
</code></pre>
<h1 id="-end-">- End -</h1>
<br />
                                            
                                </p>
                            </div>
                            <div class="post_footer">
                                
                                    <div class="meta">
                                        <div class="info"><span class="field tags"><i class="iconfont icon-tag-sm"></i>
                                                
                                                    <a href="https://github.pansis.site/tag/24hc/" class="article-info">
                                                        23航C
                                                    </a>
                                                    
                                            </span>
                                        </div>
                                    </div>
                                    
                                        
                                            <div class="next-post" style="margin-top: 20px;">
                                                <div class="next">下一篇</div>
                                                <a href="https://github.pansis.site/post/c3-jiang-jie-23-hang-c/">
                                                    <h3 class="post-title">
                                                        C3讲解-23航c
                                                    </h3>
                                                </a>
                                            </div>
                                            
                            </div>
                        </div>
                        
                            
                                <link rel="stylesheet" href="https://unpkg.com/gitalk/dist/gitalk.css">
<script src="https://unpkg.com/gitalk/dist/gitalk.min.js"></script>
<div id="gitalk-container" style="padding-bottom: 20px;"></div>
<script>
    var pageId = (location.pathname).substring(1, 49) // Ensure uniqueness and length less than 50
    pageId = pageId.endsWith('/') ? pageId.slice(0, -1) : pageId // 以斜杠结尾则去除
    var gitalk = new Gitalk({
        clientID: '9d5eba33618472c44a07',
        clientSecret: '065a85ed04333ceebfc4f01d7ca1674175730339',
        repo: 'fzxl2003.github.io',
        owner: 'fzxl2003',
        admin: ['fzxl2003'],
        id: pageId,
        distractionFreeMode: false  // Facebook-like distraction free mode
    })
    gitalk.render('gitalk-container')
</script>
                                    
                                        
                                                    
                    </div>
                </div>
            </div>
    </div>
    <div class="footer">
    
    <div class="powered_by">
        <a href="https://codeberg.org/kytrun/gridea-theme-one" target="_blank">Theme One,</a>
        <a href="https://open.gridea.dev/" target="_blank">Powered by Gridea&#65281;</a>
    </div>
    
    
        <div class="footer_slogan">
            Powered by <a href="https://github.com/getgridea/gridea" target="_blank">Gridea</a>
        </div>
    
    <div id="back_to_top" class="back_to_top">
        <span>△</span>
    </div>
    
</div>

<script src="https://github.pansis.site/media/scripts/util.js"></script>
        <link rel="stylesheet" href="//unpkg.com/@highlightjs/cdn-assets@11.5.1/styles/default.min.css">
        <script src="//unpkg.com/@highlightjs/cdn-assets@11.5.1/highlight.min.js"></script>
        <script>hljs.highlightAll();</script>
</body>

</html>